% !Mode:: "TeX:UTF-8"
% Translator: Tianfan Fu
\chapter{\glsentrytext{monte_carlo}方法}
\label{chap:monte_carlo_methods}
% 581

随机算法可以粗略的分为两类：\ENNAME{Las Vegas}算法和\gls{monte_carlo}算法。
\ENNAME{Las Vegas}算法通常精确地返回一个正确答案 （或者发布一个失败报告）。
这类方法通常需要占用随机量的计算资源（通常包括内存和运行时间）。
与此相对的，\gls{monte_carlo}方法返回一个伴随着随机量错误的答案。
花费更多的计算资源（通常包括内存和运行时间）可以减少这种随机量的错误。
在任意的固定的计算资源下， \gls{monte_carlo}算法可以得到一个近似解。

对于\gls{ML}中的许多问题来说，我们很难得到精确的答案。
这类问题很难用精确的确定性的算法如\ENNAME{Las Vegas}算法解决。
取而代之的是确定性的近似算法或\gls{monte_carlo}方法。
这两种方法在\gls{ML}中都非常普遍。
本章主要关注\gls{monte_carlo}方法。
% 581

\section{采样和\glsentrytext{monte_carlo}方法}
\label{sec:sampling_and_monte_carlo_methods}

\gls{ML}中的许多工具是基于从某种分布中采样以及用这些样本对目标量做一个\gls{monte_carlo}估计。

\subsection{为什么需要采样？}
\label{sec:why_sampling}

我们希望从某个分布中采样存在许多理由。
当我们需要以较小的代价近似许多项的和或某个积分时采样是一种很灵活的选择。
有时候，我们使用它加速一些很费时却易于处理的和的估计，就像我们使用\gls{minibatch}对整个训练成本进行subsample的情况。
在其他情况下，我们需要近似一个难以处理的和或积分，例如估计一个\gls{undirected_model}的\gls{partition_function}的对数的梯度。
在许多其他情况下，抽样实际上是我们的目标，就像我们想训练一个可以从训练分布采样的模型。
% 582 

\subsection{\glsentrytext{monte_carlo}采样的基础}
\label{sec:basics_of_monte_carlo_sampling}

当无法精确计算和或积分（例如，和具有指数数量个项，且无法被精确简化）时，通常可以使用\gls{monte_carlo}采样。
这种想法把和或者积分视作某分布下的期望，然后通过估计对应的平均值来近似这个期望。
令
\begin{align}
s = \sum_{\Vx} p(\Vx)f(\Vx) = E_p[f(\Vx)]
\end{align}
或者
\begin{align}
\label{eqn:integra}
s = \int p(\Vx)f(\Vx)d\Vx = E_p[f(\Vx)]
\end{align}
为我们所需要估计的和或者积分，写成期望的形式，$p$是一个关于随机变量$\Vx$的概率分布（求和时）或者概率密度函数（求积分时）。
% 582 

我们可以通过从$p$中采集$n$个样本$\Vx^{(1)},\ldots,\Vx^{(n)}$来近似$s$并得到一个经验平均值
\begin{align}
\hat{s}_n = \frac{1}{n}\sum_{i=1}^{n}f(\Vx^{(i)}).
\end{align}
这种近似可以被证明拥有如下几个性质。
首先很容易观察到$\hat{s}$这个估计是无偏的，由于
\begin{align}
\SetE[\hat{s}_n] = \frac{1}{n}\sum_{i=1}^{n}\SetE[f(\Vx^{(i)})] = \frac{1}{n}\sum_{i=1}^{n}s = s
\end{align}
% 582

此外，根据\firstgls{law_of_large_numbers}，如果样本$\Vx^{(i)}$独立且服从同一分布，那么其平均值几乎必然收敛到期望值，即
\begin{align}
\lim_{n\xrightarrow{}\infty} \hat{s}_n = s，
\end{align}
只需要满足各个单项的方差，即$\text{Var}[f(\Vx^{(i)})]$有界。
详细地说，我们考虑当$n$增大时$\hat{s}_n$的方差。
只要$\text{Var}[f(\Vx^{(i)})]<\infty$，方差$\text{Var}[f(\Vx^{(i)})]$减小并收敛到0：
\begin{align}
\text{Var}[\hat{s}_n] & = \frac{1}{n^2}\sum_{i=1}^{n}\text{Var}[f(\Vx)]\\
&  = \frac{\text{Var}[f(\Vx)]}{n}.
\end{align}
这个简单的结果启迪我们如果估计\gls{monte_carlo}均值中的不确定性或者说是\gls{monte_carlo}估计的期望误差。
我们计算了$f(\Vx^{(i)})$的经验均值和方差，\footnote{计算无偏估计的方差时，更倾向于用计算偏差平方和除以$n-1$而非$n$。}
然后将估计的方差除以样本数$n$来得到$\text{Var}[\hat{s}_n]$的估计。
\firstgls{central_limit_theorem}告诉我们$\hat{s}_n$的分布收敛到以$s$为均值以$\frac{\text{Var}[f(\Vx)]}{n}$为方差的正态分布。
这使得我们可以利用正态分布的累积密度函数来估计$\hat{s}_n$的置信区间。
% 583

以上的所有结论都依赖于我们可以从基准分布$p(\Vx)$中轻易的采样，但是这个假设并不是一直成立的。
当我们无法从$p$中采样时，一个备选方案是用\gls{importance_sampling}，在\secref{sec:importance_sampling_chap17}会讲到。
一种更加通用的方式是采样一系列的趋近于目标分布的估计。
这就是\gls{mcmc}方法（见\secref{sec:markov_chain_monte_carlo_methods}）。
% 583

\section{\glsentrytext{importance_sampling}}
\label{sec:importance_sampling_chap17}

如方程~\eqref{eqn:integra}所示，在\gls{monte_carlo}方法求积分（或者求和）的过程中，确定积分的哪一部分作为概率分布$p(\Vx)$，哪一部分作为被积的函数$f(\Vx)$（我们感兴趣的是估计$f(\Vx)$在概率分布$p(\Vx)$下的期望）是很关键的一步。
$p(\Vx)f(\Vx)$存在不唯一的分解因为它通常可以被写成
\begin{align}
\label{eqn:decomposition}
p(\Vx)f(\Vx) = q(\Vx) \frac{p(\Vx)f(\Vx)}{q(\Vx)},
\end{align}
在这里，我们从$q$分布中采样，然后估计$\frac{pf}{q}$在此分布下的均值。
许多情况中，给定$p$和$f$的情况下我们希望计算某个期望，这个问题既然是求期望，那么$p$和$f$最好是很常见的分解。
然而，从衡量一定采样数所达到的精度的角度说，原始定义的问题通常不是最优的选择。
幸运的是，最优的选择$q^*$通常可以简单推出。
这种最优的采样函数$q^*$对应的是最优\gls{importance_sampling}。
% 584


从\eqnref{eqn:decomposition}中所示的关系中可以发现，任意\gls{monte_carlo}估计
\begin{align}
\hat{s}_p = \frac{1}{n}\sum_{i=1,\Vx^{(i)}\sim p}^{n}f(\Vx^{(i)})
\end{align}
可以被转化为一个\gls{importance_sampling}的估计
\begin{align}
\hat{s}_q = \frac{1}{n}\sum_{i=1,\Vx^{(i)}\sim q}^{n}\frac{p(\Vx^{(i)})f(\Vx^{(i)})}{q(\Vx^{(i)})}
\end{align}
我们可以容易的发现估计值的期望与$q$分布无关
\begin{align}
\SetE_q [\hat{s}_q] = \SetE_p [\hat{s}_p] = s
\end{align}
然而，\gls{importance_sampling}的方差却对不同的$q$的选取非常敏感。
这个方差可以表示为
\begin{align}
\label{eqn:variance_of_is}
\Var [\hat{s}_q] = \Var [\frac{p(\Vx)f(\Vx)}{q(\Vx)}]/n
\end{align}
当$q$取到
\begin{align}
q^*(\Vx) = \frac{p(\Vx)\vert f(\Vx)\vert}{Z}
\end{align}
时，方差达到最小值。
% 584


在这里$Z$表示归一化常数，$Z$的选择使得$q*(\Vx)$之和或者积分为1。
一个好的\gls{importance_sampling}分布会把更多的权重放在被积函数较大的地方。
事实上，当$f(\Vx)$为一个常数的时候，$\Var[\hat{s}_{q^*}]=0$， 这意味着当使用最优的$q$分布的时候，只需要采一个样本就够了。
当然，这仅仅是因为计算$q^*$的时候已经解决了所有的问题。
所以这种只需要采一个样本的方法往往是实践中无法实现的。
% 584

对于\gls{importance_sampling}来说任意$q$分布都是可行的（从得到一个期望上正确的值的角度来说），$q^*$指的是最优的$q$分布。
从$q^*$中采样往往是不可行的，所以总是采样其它的选择来降低方差。
% 584



另一种方法是采用\firstgls{biased_importance_sampling}，这种方法有一个优势并不需要归一化的$p$或$q$分布。
在处理离散变量的时候，有偏\gls{importance_sampling}估计可以表示为
\begin{align}
\label{eqn:bis}
\hat{s}_{\text{BIS}} & = \frac{\sum_{i=1}^{n} \frac{p(\Vx^{(i)})}{q(\Vx^{(i)})} f(\Vx^{(i)})}{\sum_{i=1}^{n}\frac{p(\Vx^{(i)})}{q(\Vx^{(i)})}} \\
& = \frac{\sum_{i=1}^{n} \frac{p(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})} f(\Vx^{(i)})}{\sum_{i=1}^{n}\frac{p(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})}} \\
& = \frac{\sum_{i=1}^{n} \frac{\tilde{p}(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})} f(\Vx^{(i)})}{\sum_{i=1}^{n}\frac{\tilde{p}(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})}}
\end{align}
其中$\tilde{p}$和$\tilde{q}$分别是分布${p}$和${q}$的未经归一化的形式，$x^{(i)}$是从分布${q}$中采集的样本。
这种估计是有偏的因为$\SetE[\hat{s}_{\text{BIS}}]\neq s$，除了当$n$渐进性地趋近于$\infty$时，方程~\eqref{eqn:bis}的分母收敛到1。
所以这种估计也被叫做的渐进性无偏的。
% 585

尽管一个好的$q$分布的选择可以显著的提高\gls{monte_carlo}估计的效率，反之一个糟糕的$q$分布的选择则会使效率更糟糕。
我们回过头来看看方程~\eqref{eqn:variance_of_is}会发现，如果存在一个$q$使得$\frac{p(\Vx)f(\Vx)}{q(\Vx)}$很大，那么这个估计的方差也会很大。
当$q(\Vx)$很小，而$f(\Vx)$和$p(\Vx)$都较大并且无法抵消$q$时，这种情况会非常明显。
$q$分布经常会取一些简单常用的分布使得我们能够从$q$分布中容易的采样。
当$\Vx$是高维数据的时候，$q$分布的简单性使得它很难于$p$或者$p\vert f\vert$相匹配。
当$q(x^{(i)})\gg p(x^{(i)}) \vert f(x^{(i)})\vert $的时候，\gls{importance_sampling}采到了很多无用的样本（权值之和很小或趋于零）。
另一方面，当$q(x^{(i)})\ll p(x^{(i)}) \vert f(x^{(i)})\vert $的时候， 样本会很少被采到，其对应的权值却会非常大。
正因为后一个事件是很少发生的，这些样本很难被采到，通常使得对$s$的估计出现了估计不足，于之前过度估计相对。
这样的不均匀情况在高维数据屡见不鲜，因为在高维度分布中联合分布的动态域通常非常大。
% 585

尽管存在上述的风险，但是\gls{importance_sampling}及其变种在\gls{ML}中的应用中仍然扮演着重要的角色，包括\gls{DL}问题。
比方说，\gls{importance_sampling}被应用于加速训练大规模词汇神经网络的过程中（见\secref{sec:importance_sampling_chap12}）或者其它有着大量输出结点的\gls{NN}中。
此外，还可以看到\gls{importance_sampling}应用于估计\gls{partition_function}（一个概率分布的归一化常数）的过程中（详见\secref{sec:estimating_the_partition_function}）以及在深度有向图模型比如\gls{VAE}中估计似然函数的对数（详见\secref{sec:variational_autoencoders}）。
采用\gls{SGD}训练模型参数的时候\gls{importance_sampling}可以用来改进对\gls{cost_function}的梯度的估计，尤其是针对于分类器模型的训练中一小部分错误分类样本产生的\gls{cost_function}。
在这种情况下更加频繁的采集这些困难的样本可以降低梯度的估计的方差\citep{Hinton06}。
% 586 


\section{\glsentrytext{mcmc}方法}
\label{sec:markov_chain_monte_carlo_methods}

在许多实例中，我们希望采用\gls{monte_carlo}方法，然而往往又不存在一种直接从目标分布$p_{\text{model}}(\Vx)$中精确采样或者一个好的（方差较小的）\gls{importance_sampling}分布$q(\Vx)$。
在深度学习的例子中，分布$p_{\text{model}}(\Vx)$往往表达成一个无向的模型。
在这种情况下，为了从分布$p_{\text{model}}(\Vx)$中近似采样，我们引入了一种数学工具，它被命名为\firstgls{markov_chain}。
利用\gls{markov_chain}来进行\gls{monte_carlo}估计的这一类算法被称为\firstgls{mcmc}算法。
\gls{mcmc}算法在\gls{ML}中的应用在\citep{koller-book2009}中花了大量篇幅描述。
\gls{mcmc}算法的最标准的要求是只适用模型分布处处不为0的情况。
因此，最方便的目标分布的表达是从\firstgls{energy_based_model}即$p(\Vx)\propto \exp(-E(\Vx))$中采样，见\secref{sec:energy_based_models}。
在\gls{energy_based_model}中每一个状态所对应的概率都不为零。
事实上\gls{mcmc}方法可以被广泛的应用在了许多包含概率为0的状态的概率分布中。
然而，在这种情况下，关于\gls{mcmc}方法性能的理论保证只能依据具体情况具体分析。
在\gls{DL}中，应用于\gls{energy_based_model}的通用的理论分析是很常见的。
% 586 end


为了解释从\gls{energy_based_model}中采样的困难性，我们考虑一个包含两个变量的\gls{energy_based_model}的例子，记作$p(a,b)$。
为了采$a$，我们必须先从$p(a\vert b)$中采样，为了采$b$，我们又必须从$p(b\vert a)$中采样。
这似乎成了难以解释的先有鸡还是先有蛋的问题。
\gls{directed_model}避免了这一问题因为它的图是有向无环的。
为了以拓扑顺序完成对包含各个变量的一个样本的\firstgls{ancestral_sampling}，给定每个变量的所有父结点的条件下，这个变量是确定能够被采样的（详见\secref{sec:sampling_from_graphical_models}）。
\gls{ancestral_sampling}定义了一种高效的，单路径的方法来采集一个样本。
% 587 begin


在\gls{energy_based_model}中，我们通过使用\gls{markov_chain}来采样，从而避免了先有鸡还是先有蛋的问题。
\gls{markov_chain}的核心思想是以一个任意状态的点$\Vx$作为起始点。
随着时间的推移，我们随机的反复的更新状态$\Vx$。
最终$\Vx$成为了一个从$p(\Vx)$中抽出的（接近）比较公正的样本。
在正式的定义中，\gls{markov_chain}由一个随机状态$x$和一个转移分布$T(\Vx'\vert \Vx)$定义而成，$T(\Vx'\vert \Vx)$是一个概率分布，说明了给定状态$\Vx$的情况下随机的转移到$\Vx'$的概率。
运行一个\gls{markov_chain}意味着根据转移分布$T(\Vx'\vert \Vx)$反复的用状态$\Vx'$来更新状态$\Vx$。
% 587


为了给出\gls{mcmc}方法的一些理论解释，重定义这个问题是很有用的。
首先我们关注一些简单的情况，其中随机变量$\Vx$有可数个状态。
我们将这种状态记作正整数$x$。
不同的整数$x$的大小对应着原始问题中$\Vx$的不同状态。
% 587  


接下来我们考虑如果并行的运行无穷多个\gls{markov_chain}会发生什么。
不同\gls{markov_chain}的所有的状态都会被某一个分布$q^{(t)}(x)$采到，在这里$t$表示消耗的时间数。
开始时，对每个\gls{markov_chain}，我们采用一个分布$q^{{0}}$来任意的初始化$x$。
之后，$q^{(t)}$与所有之前跑过的\gls{markov_chain}有关。
我们的目标就是$q^{(t)}(x)$收敛到$p(x)$。
% 587 

因为我们已经用正整数$x$重定义了这个问题，我们可以用一个向量$\Vv$来描述这个概率分布$q$，并且满足
\begin{align}
q(x = i) = v_i
\end{align}
% 587

然后我们考虑从状态$x$到状态$x'$更新单一的\gls{markov_chain}。
单一状态转移到$x'$的概率可以表示为
\begin{align}
\label{eqn:transition1}
q^{(t+1)}(x') = \sum_{x} q^{(t)}(x) T(x'\vert x)
\end{align}
% 587


根据状态为整数的设定，我们可以将转移算子$T$表示成一个矩阵$\MA$。
矩阵$\MA$的定义如下：
\begin{align}
\MA_{i,j} = T(\Vx' = i\vert \Vx = j)
\end{align}
使用这一定义，我们可以重新写成\eqnref{eqn:transition1}。
与之前使用$q$和$T$来理解单个状态的更新相对的是，我们现在可以使用$\Vv$和$\MA$来描述当我们更新时（并行运行的）不同个\gls{markov_chain}上的整个分布是如何变化的：
\begin{align}
\Vv^{(t)} = \MA \Vv^{(t-1)}
\end{align}
% 588

重复的使用\gls{markov_chain}来更新就相当于重复的乘上矩阵$\MA$。
换一句话说，我们可以认为这一过程就是$\MA$的指数变化：
\begin{align}
\Vv^{(t)} = \MA^{t} \Vv^{(0)}
\end{align}
% 588

矩阵$\MA$有一种特殊的结构，因为它的每一列都代表了一个概率分布。
这样的矩阵被称作是\firstgls{stochastic_matrix}。
对于任意状态$x$到任意其它状态$x'$存在一个$t$使得转移概率不为0，那么Perron-Frobenius定理~\citep{perron1907theorie,frobenius1908matrizen}可以保证这个矩阵的最大特征值是实数且大小为1。
我们可以看到所有的特征值随着时间呈现指数变化：
\begin{align}
\Vv^{(t)} = (\MV \text{diag}(\lambda)\MV^{-1})^{t} \Vv^{(0)}
 = \MV \text{diag}(\lambda)^t \MV^{-1} \Vv^{(0)}
\end{align}
% 588


这个过程导致了所有的不等于1的特征值都衰减到0。
在一些较为宽松的假设下，我们可以保证矩阵$\MA$只有一个特征值为1。
所以这个过程收敛到\firstgls{stationary_distribution}，有时也叫做\firstgls{equilibrium_distribution}。
收敛时，我们得到
\begin{align}
\label{eqn:1723}
\Vv ' = \MA \Vv = \Vv 
\end{align}
这个条件也适用于收敛之后的每一步。
这就是特征向量方程。
作为收敛的静止点，$\Vv$一定是特征值为1所对应的特征向量。
这个条件保证了收敛到了\gls{stationary_distribution}以后，之后的采样过程不会改变不同的\gls{markov_chain}的状态的分布（尽管转移算子不会改变每个单独的状态）。
% 588

如果我们正确的选择了转移算子$T$，那么最终的\gls{stationary_distribution}$q$将会等于我们所希望采样的分布$p$。
我们会简要的介绍如何选择$T$，详见\secref{sec:gibbs_sampling}。
% 588


可数状态\gls{markov_chain}的大多数的性质可以被推广到连续状态的\gls{markov_chain}中。
在这种情况下，一些研究者把\gls{markov_chain}叫做\firstgls{harris_chain}，但是这两种情况我们都用\gls{markov_chain}来表示。
通常情况下，在一些宽松的条件下，一个带有转移算子$T$的\gls{markov_chain}都会收敛到一个固定点，这个固定点可以写成如下形式：
\begin{align}
q' (\Vx') = \SetE_{\Vx\sim q}T(\Vx'\vert \Vx)
\end{align}
这个方程的离散版本就是方程~\eqref{eqn:1723}。	
当$\Vx$离散时，这个期望对应着求和，而当$\Vx$连续时，这个期望对应的是积分。
% 589 head



无论状态是连续还是离散，所有的\gls{markov_chain}方法都包括了重复，随机的更新直到最终所有的状态开始从\gls{equilibrium_distribution}采样。
运行\gls{markov_chain}直到它达到\gls{equilibrium_distribution}的过程通常被叫做\gls{markov_chain}的\firstgls{burn_in}过程。
在\gls{markov_chain}达到\gls{equilibrium_distribution}之后，我们可以从\gls{equilibrium_distribution}中采集一个无限多数量的样本序列。
这些样本服从同一分布，但是两个连续的样本之间存在强烈的相关性。
所以一个有限的序列无法完全表达\gls{equilibrium_distribution}。
一种解决这个问题的方法是每隔$n$个样本返回一个样本，从而使得我们对于\gls{equilibrium_distribution}的统计量的估计不会被\gls{mcmc}方法的样本之间的相关性所干扰。
所以\gls{markov_chain}在计算上是非常昂贵的，主要源于需要预烧的时间以及在达到\gls{equilibrium_distribution}之后从一个样本转移到另一个完全无关的样本所需要的时间。
如果我们想要得到完全独立的样本，那么我们需要同时并行的运行多个\gls{markov_chain}。
这种方法使用了额外的并行计算来消除潜在因素的干扰。
使用一条\gls{markov_chain}来生成所有样本的策略和每条\gls{markov_chain}只产生一个样本的策略是两种极端。
深度学习的研究者们通常选取的\gls{markov_chain}的数目和\ENNAME{minibatch}中的样本数相近，然后从这些\gls{markov_chain}的集合中采集所需要的样本。
常用的\gls{markov_chain}的数目通常选为100。
% 589

另一个难点是我们无法预先知道\gls{markov_chain}需要运行多少步才能到达\gls{equilibrium_distribution}。 
这段时间通常被称为\firstgls{mixing_time}。
检测一个\gls{markov_chain}是否达到平衡是很困难的。
我们并没有足够完善的理论来解决这个问题。
理论只能保证\gls{markov_chain}会最终收敛，但是无法保证其它。
如果我们从矩阵$\MA$作用在概率向量$\Vv$的角度来分析\gls{markov_chain}，那么我们可以发现当$\MA^t$除了1以外的特征值都趋于0的时候，\gls{markov_chain}收敛到了\gls{equilibrium_distribution}。
这也意味着矩阵$\MA$的第二大的特征值决定了\gls{markov_chain}的混合时间。
然而，在实践中，我们通常不能将\gls{markov_chain}表示成为矩阵的形式。
我们的概率模型所能够达到的状态是变量数的指数级别，所以表达$\Vv$，$\MA$或者$\MA$的特征值是不现实的。
由于这些阻碍，我们通常无法知道\gls{markov_chain}是否以及收敛。
作为替代，我们只能运行足够长时间\gls{markov_chain}直到我们粗略估计是足够的，然后使用启发式的方法来决定\gls{markov_chain}是否收敛。
这些启发性的算法包括了手动检查样本或者衡量连续样本之间的相关性。
% 590 head



\section{\glsentrytext{gibbs_sampling}}
\label{sec:gibbs_sampling}

截至目前我们已经了解了如何通过反复的更新$\Vx \xleftarrow{} \Vx'\sim T(\Vx'\vert\Vx)$从一个分布$q(\Vx)$中采样。
然而我们还没有提到过如何确定一个有效的$q(\Vx)$分布。
本书中描述了两种基本的方法。
第一种方法是从已经学习到的分布$p_{\text{model}}$中推导出$T$，就像下文描述的从\gls{energy_based_model}中采样的案例一样。
第二种方法是直接用参数描述$T$，然后学习这些参数，其\gls{stationary_distribution}隐式地定义了我们所感兴趣的模型$p_{\text{model}}$。
我们将在\secref{sec:generative_stochastic_networks}和\secref{sec:other_generation_schemes}中讨论第二种方法的例子。
% 590


在\gls{DL}中，我们通常使用\gls{markov_chain}从定义为\gls{energy_based_model}的分布$p_{\text{model}}(\Vx)$中采样。
在这种情况下，我们希望\gls{markov_chain}的$q(\Vx)$分布就是$p_{\text{model}}(\Vx)$。
为了得到所期望的$q(\Vx)$分布，我们必须选取合适的$T(\Vx'\vert \Vx)$。
% 590


\firstgls{gibbs_sampling}是一种概念简单而又有效的方法来构造一个从$p_{\text{model}}(\Vx)$中采样的\gls{markov_chain}，其中在\gls{energy_based_model}中从$T(\Vx'\vert \Vx)$采样是通过选择一个变量$x_i$然后从$p_{\text{model}}$中的该点在无向图$G$中邻接点的条件分布中抽样。
给定他们的邻居结点只要一些变量是条件独立的，那么这些变量可以被同时采样。
正如在\secref{sec:example_the_restricted_boltzmann_machine}中看到的\gls{RBM}的例子一样，\gls{RBM}所有的隐层结点可以被同时采样，因为在给定可见层结点的条件下他们相互条件独立。
同样的，所有的可见层结点也可以被同时采样因为在给定隐藏层结点的情况下他们相互条件独立。
像这样的同时更新许多变量的\gls{gibbs_sampling}通常被叫做\firstgls{block_gibbs_sampling}。
% 590

设计从$p_{\text{model}}$中采样的\gls{markov_chain}还存在另外的备选方法。
比如说，Metropolis-Hastings算法在其它情景下被广泛使用。
在\gls{DL}的\gls{undirected_model}中，除了\gls{gibbs_sampling}很少使用其它的方法。
改进采样技巧也是一个潜在的研究热点。
% 590


\section{不同的峰值之间的\glsentrytext{mixing}挑战}
\label{sec:the_challenge_of_mixing_between_separated_modes}
% 591

使用\gls{mcmc}方法的主要难点在于他们经常\gls{mixing}的很慢。
理想情况下，从\gls{markov_chain}中采出的连续的样本之间是完全独立的，而且在$\Vx$空间中，\gls{markov_chain}以正比于不同区域对应的概率的概率访问不同区域。
然而，在高维的情况下，\gls{mcmc}方法采出的样本可能会具有很强的相关性。
我们把这种现象称为慢\gls{mixing}甚至\gls{mixing}失败。
<bad>具有缓慢\gls{mixing}的\gls{mcmc}方法可以被视为对\gls{energy_function}无意地执行类似于带噪声的\gls{GD}的事物，或者相对于链的状态（随机变量被采样）对概率进行等效的噪声爬坡。
从$\Vx^{(t-1)}$到$\Vx^{(t)}$该链倾向于选取了很小的步长（在\gls{markov_chain}的状态空间中），其中能量$E(\Vx^{(t)})$通常低于或者近似等于能量$E(\Vx^{(t-1)})$，倾向于产生较低能量的移动。
当从可能性较小的状态（比来自$p(\Vx)$的典型样本拥有更高的能量）开始时，链趋向于逐渐减少状态的能量，并且仅仅偶尔移动到另一个峰值。
一旦该链已经找到低能量的区域（例如，如果变量是图像中的像素，则低能量的区域可以是同一对象的图像的相连的流形），我们称之为峰值，链将倾向于围绕着这个峰值游走（以某一种形式的随机游走）。
有时候，它会远离该峰值，通常返回该峰值或者（如果找到一条离开的路线）移向另一个峰值。
问题是对于很多有趣的分布来说成功的离开路线很少，所以\gls{markov_chain}将在一个峰值附近抽取远超过需求的样本。
% 591 


当考虑到\gls{gibbs_sampling}算法（见\secref{sec:gibbs_sampling}）时，这种现象格外明显。
在这种情况下，我们考虑在一定步数内从一个峰值走向移动到一个临近的峰值的概率。
决定这个概率的是两个峰值之间的``能量障碍''的形状。
隔着一个巨大的``能量障碍'' （低概率的区域）的两个峰值之间的转移的概率是（随着能量障碍的高度）指数下降的，如在\figref{fig:chap17_good_bad_really_bad_mixing_color}中展示的一样。
当目标分布有很多峰值并且以很高的概率被低概率区域所分割，尤其当\gls{gibbs_sampling}的每一步都只是更新变量的一小部分而这一小部分又严重依赖其它的变量时，这会导致严重的问题。
% 591


\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
	\centerline{\includegraphics{Chapter17/figures/good_bad_really_bad_mixing_color}}
\fi
	\caption{Tmp}
	\label{fig:chap17_good_bad_really_bad_mixing_color}
\end{figure}


举一个简单的例子，考虑两个变量$a$, $b$的\gls{energy_based_model}，这两个变量都是二元的，取值$+1$或者$-1$。
如果对某个较大的正数$w$, $E(a,b) = - w a b$，那么这个模型传达了一个强烈的信息，$a$和$b$有相同的符号。
当$a=1$时用\gls{gibbs_sampling}更新$b$。
给定$b$时的条件分布满足$p(b=1\vert a=1) = \sigma(w)$。
如果$w$的值很大，sigmoid趋近于饱和，那么$b$取到1的概率趋近于1。
相同的道理，如果$a=-1$，那么$b$取到$-1$的概率也趋于1。
根据模型$p_{\text{model}}(a,b)$，两个变量取一样的符号的概率几乎相等。
根据$p_{\text{model}}(a\vert b)$，两个变量应该有相同的符号。
这也意味着\gls{gibbs_sampling}很难会改变这些变量的符号。
% 592

在实际问题中，这种挑战更加的艰巨因为在实际问题中我们不能仅仅关注在两个峰值之间的转移而是在多个峰值之间。
如果几个这样的转移是很艰难的，那么很难得到一些覆盖大部分峰值的样本集合，同时\gls{markov_chain}收敛到它的\gls{stationary_distribution}的过程也会非常缓慢。
% 592

通过寻找一些相互独立的组以及分块同时更新各组的变量，这个问题有时候可以被解决的。
然而不幸的是，当依赖关系很复杂的时候，从这些组中采样的过程从计算角度上说过于复杂。
归根结底，\gls{markov_chain}最初就是被提出来解决这个问题，即从大组的变量中采样的问题。
% 592

在含有隐含变量的模型中，其中定义来一个联合分布$p_{\text{model}}(\Vx,\Vh)$，我们经常通过交替的从$p_{\text{model}}(\Vx\vert \Vh)$和$p_{\text{model}}(\Vh\vert \Vx)$中采样来达到抽$\Vx$的目的。
从快速\gls{mixing}的角度上说，我们更希望$p_{\text{model}}(\Vh\vert \Vx)$有很大的熵。
然而，从学习一个$\Vh$的有用表示的角度上考虑，我们还是希望$\Vh$能够包含$\Vx$的足够的信息从而能够较完整的重构它，这意味$\Vh$和$\Vx$有着非常高的互信息。
这两个目标是相互矛盾的。
我们经常学习到一些有很强编码能力的生成模型，但是无法很好的\gls{mixing}。
这种情况在\gls{BM}中经常出现，\gls{BM}学到到分布越尖锐，该分布的\gls{markov_chain}的采样越难\gls{mixing}的好。
这个问题在\figref{fig:chap17_fig-dbm-bad-mixing}中有所描述。
% 593

\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
	\centerline{\includegraphics{Chapter17/figures/fig-adversarial}}
	\centerline{\includegraphics{Chapter17/figures/fig-dbm-bad-mixing}}	
\fi
	\caption{Tmp}
	\label{fig:chap17_fig-dbm-bad-mixing}
\end{figure}


当感兴趣的分布具有对于每个类具有单独的流行结构时，所有这些问题可以使MCMC方法不那么有用：分布集中在许多峰值周围，并且这些模式由大量高能量区域分割。
我们在许多分类问题中遇到的是这种类型的分布，它将使得MCMC方法非常缓慢地收敛，因为峰值之间的\gls{mixing}缓慢。
% 593



\subsection{不同峰值之间通过\glsentrytext{tempering}来\glsentrytext{mixing}}
\label{sec:tempering_to_mix_between_modes}
% 594

当一个分布有一些陡峭的峰值并且它们的周围伴随着概率较低的区域时，很难在不同的峰值之间\gls{mixing}。
一些加速\gls{mixing}的方法是基于构造一个不同的概率分布，这个概率分布的峰值没有那么高，峰值周围的低谷也没有那么低。
\gls{energy_based_model}为这个想法提供一种简单的做法。
截止目前，我们已经描述了一个\gls{energy_based_model}的概率分布的定义：
\begin{align}
\label{eqn:1725}
p(\Vx) \propto \exp(-E(\Vx)).
\end{align}
\gls{energy_based_model}可以通过添加一个额外的控制峰值尖锐程度的参数$\beta$来加强：
\begin{align}
\label{eqn:1726}
p_{\beta}(\Vx) \propto \exp(-\beta E(\Vx)).
\end{align}
$\beta$参数可以被理解为\firstgls{temperature}的倒数，在统计物理中反映了\gls{energy_based_model}的本质。
当\gls{temperature}趋近于0时，$\beta$趋近于无穷大，此时的\gls{energy_based_model}是确定性的。
当\gls{temperature}趋近于无穷大时，$\beta$趋近于零，\gls{energy_based_model}（对离散的$\Vx$）成了均匀分布。
% 594

通常情况下，在$\beta = 1$的情况下训练一个模型。
然而，我们利用了其它\gls{temperature}，尤其是$\beta < 1$的情况。
\firstgls{tempering}是一种通用的策略，通过从$\beta<1$模型中采样来在$p_1$的不同峰值之间快速\gls{mixing}。
% 594

基于\gls{tempering}转移的\gls{markov_chain}\citep{Neal94b}初始从高\gls{temperature}的分布中采样使得在不同的峰值之间\gls{mixing}，然后从\gls{temperature}为1的分布中采样。
这些技巧被应用在\gls{RBM}中\citep{Salakhutdinov-2010}。
另一种方法是利用\gls{parallel_tempering}\citep{Iba-2001}。
其中\gls{markov_chain}并行的模拟许多不同\gls{temperature}的不同的状态。
最高\gls{temperature}的状态\gls{mixing}较慢，相比之下最低\gls{temperature}的状态，即\gls{temperature}为1时，采出了精确的样本。
转移算子包括了两个\gls{temperature}之间随机的跳转，所以一个高\gls{temperature}状态分布的样本有足够大的概率跳转到低\gls{temperature}的分布中。
这个方法也被应用到了\gls{RBM}中\citep{Desjardins+al-2010-small,Cho10IJCNN}。
尽管\gls{tempering}这种方法前景可期，现今它仍然无法让我们在采样复杂的\gls{energy_based_model}中更进一步。
一个可能的原因是在\firstgls{critical_temperatures}时\gls{temperature}转移算子必须设置的非常小（因为\gls{temperature}需要逐渐的下降）来确保\gls{tempering}的有效性。
% 594



% 595
\subsection{深度也许会有助于\glsentrytext{mixing}}
\label{sec:depth_may_help_mixing}

当我们从隐变量模型$p(\Vh,\Vx)$中采样的时候，我们可以发现如果$p(\Vh\vert \Vx)$将$\Vx$编码的非常好，那么从$p(\Vx \vert \Vh)$中采样的时候，并不会太大的改变$\Vx$，那么\gls{mixing}结果会很糟糕。
解决这个问题的一种方法是使得$\Vh$成为一种将$\Vx$编码为$\Vh$的深度表达，从而使得\gls{markov_chain}在$\Vh$空间中更快的\gls{mixing}。
在许多表达学习的算法诸如自编码器（autoencoder）和\gls{RBM}中，$\Vh$的边缘分布并不像$\Vx$的原始数据分布，反而通常表现为均匀的单一峰值的分布。
<bad> 值得指出的是，这些方法往往利用所有可用的表达空间并尽量减小重构误差，因为当训练集上的不同样本能够被非常容易的在$\Vh$空间区分的时候，我们也会很容易的最小化重构误差。
<bad> \citep{Bengio-et-al-ICML2013-small}观察到这样的现象，带有正则项的堆叠越深的自编码器或者\gls{RBM}，顶端$\Vh$空间的边缘分布越趋向于均匀分布，而且不同峰值（比如说实验中的类别）所对应的区域之间的间距也会越模糊。
在高层次的空间训练\gls{RBM}使得\gls{gibbs_sampling}\gls{mixing}的更快。
如何利用这种观察到的现象来辅助训练深度生成模型或者从中采样仍然有待探索。
% 595

尽管存在\gls{mixing}的难点，\gls{monte_carlo}技巧仍然是一个有用的也是可用的最好的工具。
事实上，在遇到难以处理的\gls{undirected_model}的\gls{partition_function}的时候，\gls{monte_carlo}方法仍然是最基础的工具，这将在下一章详细阐述。
% 595












